1760F - Quests - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define vll vector<ll>
#define vpl vector<pair<ll, ll>>
#define all(x) x.begin(), x.end()
#define fr(n) for(ll i=0;i<(n);i++)
#define frr(k, n) for(ll j=(k); j<(n); j++)
#define lcm(a,b) (a*b)/__gcd(a,b)
#define lz(x) 31-__builtin_clz(x)
#define endl "\n"
#define ff first
#define ss second
using namespace std;
mt19937 rng((ll)std::chrono::steady_clock::now().time_since_epoch().count());
const ll N=2e5+5, mod=1e9+7;

void error(){
    ll n, c, d; cin>>n>>c>>d;
    vll a(n); fr(n){cin>>a[i];}

    sort(all(a), greater<ll>());

    ll r=0;
    for(ll i=0; i<n && i<d; i++){
        r+=a[i];
    }
    if(a[0]*d < c){
        cout<<"Impossible"<<endl;
        return;
    }
    if(r>=c){
        cout<<"Infinity"<<endl;
        return;
    }
    ll l=0, h=d;
    while(l<=h){
        ll mid=(l+h)/2;
        ll rem=0;
        for(ll i=0; i<n&&i<=mid; i++){
            rem+=a[i];
        }
        ll r_rem=(d/(mid+1)), g=(d%(mid+1));
        rem*=r_rem;
        for(ll i=0; i<n&&i<g; i++){
            rem+=a[i];
        }
        if(rem<c){
            h=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l-1<<endl;
}

int main(){
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--){error();}
return 0;
}